import java.util.*;

public class Practice1 {
    /*
    链接https://www.nowcoder.com/practice/4edf6e6d01554870a12f218c94e8a299?tpId=196&tqId=37562&ru=/exam/oj
    感觉难度不是中等难度, 难度更高, 使用贪心 + 优先级队列的方式来进行优化
    可以参考调度1, 先进行了排序, 时间复杂度nlogn
    然后用堆来优化
     */
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        Time[] times = new Time[n];
        //填写信息
        for(int i = 0;i < n;i++){
            times[i] = new Time(startEnd[i][0],startEnd[i][1]);
        }
        //使用减号会直接发生溢出, 所以使用Integer提供的方法进行比较操作, 这题的数据范围比较大
        Arrays.sort(times,(o1, o2) -> {
            return Integer.compare(o1.startTime,o2.startTime);
        });
        //堆加贪心的方法来进行维护
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.offer(times[0].endTime);
        for(int i = 1;i < n;i++){
            int cur = heap.peek();
            if(times[i].startTime >= cur){
                heap.poll();
            }
            heap.offer(times[i].endTime);
        }
        //返回堆的数量, 可以知道有几个人
        return heap.size();
    }
}
class Time{
    int startTime;
    int endTime;
    public Time(int startTime,int endTime){
        this.startTime = startTime;
        this.endTime = endTime;
    }
}